Maximum Number of Balloons

LeetCode 1297 | Difficulty: Easy

Easy

Problem Description

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

- `1 <= text.length <= 10^4`

- `text` consists of lower case English letters only.

Note: This question is the same as 2287: Rearrange Characters to Make Target String.

Topics: Hash Table, String, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 68 ms)

Metric	Value
Runtime	68 ms
Memory	36.2 MB
Date	2021-11-28

Solution

public class Solution {
    public int MaxNumberOfBalloons(string text) {
        int[] counts = new int[26];
    int[] balloonCounts = new int[26];
    foreach (var c in "balloon")
    {
        counts[c-'a']++;
    }
    
    foreach (var c in text)
    {
        balloonCounts[c-'a']++;
    }
    
    int min = Int32.MaxValue;
    foreach (var c in "balon")
    {
        
        min = Math.Min(min, balloonCounts[c-'a']/counts[c-'a']);
    }
    
    return min;
    }
}

📜 1 more C# submission(s)

Submission (2020-01-03) — 84 ms, 26.2 MB

public class Solution {
    public int MaxNumberOfBalloons(string text)
{
    char[] s = "balloon".ToCharArray();
    Dictionary<char, int> d1 = new Dictionary<char, int>();
    Dictionary<char, int> d2 = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (d1.ContainsKey(c))
        {
            d1[c]++;
        }
        else
        {
            d1.Add(c, 1);
        }
    }
    foreach (char c in text)
    {
        if (s.Contains(c))
        {
            if (d2.ContainsKey(c))
            {
                d2[c]++;
            }
            else
            {
                d2.Add(c, 1);
            }
        }
    }
    int min = Int32.MaxValue;
    foreach (var item in d1)
    {
        if(!d2.ContainsKey(item.Key)) return 0;
        min = Math.Min(d2[item.Key]/item.Value, min);
    }
    return min;
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Count the frequency of letters in the given string.

Hint 2: Find the letter than can make the minimum number of instances of the word "balloon".